package 剑指offer;

import java.util.Stack;

/**
 * @author zhangmin
 * @create 2021-11-11 17:07
 *
 * 1.栈与队列
 */
public class day1_09_30 {

    /**===========================================================================================================================
     * 剑指 Offer 09. 用两个栈实现队列
     * 插入元素时，直接插入到stack1中，在取出对头元素时，先将stack1中的元素取出放到stack2中，此时stack2中元素就是先进先出的顺序
     * */
    class CQueue {
        private Stack<Integer> stack1,stack2;
        public CQueue() {
            stack1=new Stack<>();
            stack2=new Stack<>();
        }
        //在队尾插入
        public void appendTail(int value) {
            stack1.push(value);
        }

        //在对头删除
        public int deleteHead() {
            if(stack2.isEmpty()){
                //当 s2 为空时，可以把 s1 的所有元素取出再添加进 s2，这时候 s2 中元素就是先进先出顺序了。
                while (!stack1.isEmpty())
                    stack2.push(stack1.pop());
            }
            if (stack2.isEmpty()) return -1;
            return stack2.pop();
        }
    }


    /**===========================================================================================================================
     * 剑指 Offer 30. 包含min函数的栈
     * 最小栈
     * 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
     * */
    class MinStack {
        int min=Integer.MAX_VALUE;
        Stack<Integer> stack=new Stack<>();
        /** initialize your data structure here. */
        public MinStack() {

        }
        public void push(int x) {
            if (x<=this.min){
                this.stack.push(min);
                min=x;
            }
            stack.push(x);
        }
        public void pop() {
            if (stack.pop()==min)
                min=stack.pop();
        }
        public int top() {
            return stack.peek();
        }
        public int min() {
            return this.min;
        }
    }
}
